//请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
// [[''a'',''b'',''c'',''e''],
// [''s'',''f'',''c'',''s''],
// [''a'',''d'',''e'',''e'']]
//但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
//示例 1：
//输入：board = [[''A'',''B'',''C'',''E''],[''S'',''F'',''C'',''S''],[''A'',''D'',''E'',''E'']], word = ''ABCCED''
//输出：true
//示例 2：
//输入：board = [[''a'',''b''],[''c'',''d'']], word = ''abcd''
//输出：false
//提示：
//1 <= board.length <= 200
//1 <= board[i].length <= 200

// 利用回溯方式进行查找
package main

import (
	"fmt"
)

func findPath(board [][]byte, word string, dir int, ij []int, serNum int, site [][]int) bool {
	if board[ij[0]][ij[1]] == word[serNum] {
		if serNum == len(word)-1 {
			return true
		}
		if dir != 1 {
			newij := []int{ij[0], ij[1]}
			newij[0] -= 1
			if newij[0] > -1 {
				if site[newij[0]][newij[1]] != 1 {
					site[newij[0]][newij[1]] = 1
					if findPath(board, word, 2, newij, serNum+1, site) {
						return true
					} else {
						site[newij[0]][newij[1]] = 0
					}
				}
			}
		}
		if dir != 2 {
			newij := []int{ij[0], ij[1]}
			newij[0] += 1
			if newij[0] < len(board) {
				if site[newij[0]][newij[1]] != 1 {
					site[newij[0]][newij[1]] = 1
					if findPath(board, word, 1, newij, serNum+1, site) {
						return true
					} else {
						site[newij[0]][newij[1]] = 0
					}
				}
			}
		}
		if dir != 3 {
			newij := []int{ij[0], ij[1]}
			newij[1] -= 1
			if newij[1] > -1 {
				if site[newij[0]][newij[1]] != 1 {
					if site[newij[0]][newij[1]] != 1 {
						site[newij[0]][newij[1]] = 1
						if findPath(board, word, 4, newij, serNum+1, site) {
							return true
						} else {
							site[newij[0]][newij[1]] = 0
						}

					}
				}
			}
		}

		if dir != 4 {
			newij := []int{ij[0], ij[1]}
			newij[1] += 1
			if newij[1] < len(board[0]) {
				if site[newij[0]][newij[1]] != 1 {
					site[newij[0]][newij[1]] = 1
					if findPath(board, word, 3, newij, serNum+1, site) {
						return true
					} else {
						site[newij[0]][newij[1]] = 1
					}
				}
			}
		}
	}
	return false
}

func exist(board [][]byte, word string) bool {
	ij := []int{0, 0}
	beforeDir := 0
	res := false
	for i, val := range board {
		for j, realVal := range val {
			// 二维切片
			site := make([][]int, len(board), len(board))
			for i, _ := range site {
				site[i] = make([]int, len(board[0]), len(board[0]))
			}
			if realVal == word[0] {
				ij[0] = i
				ij[1] = j
				site[ij[0]][ij[1]] = 1
			 if findPath(board, word, beforeDir, ij, 0, site){
			 	return true
			 }
			}
		}
	}
	return res
}

func main() {
	board := [][]byte{{'a', 'b'}, {'c', 'd'}}
	word := "cdba"
	fmt.Println(exist(board, word))
}
